//购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。 
//
// 示例 1： 
//
// 
//输入：price = [3, 9, 12, 15], target = 18
//输出：[3,15] 或者 [15,3]
// 
//
// 示例 2： 
//
// 
//输入：price = [8, 21, 27, 34, 52, 66], target = 61
//输出：[27,34] 或者 [34,27]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= price.length <= 10^5 
// 1 <= price[i] <= 10^6 
// 1 <= target <= 2*10^6 
// 
//
// Related Topics 数组 双指针 二分查找 👍 297 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-05-18 14:42:52
 * @description LCR 179.查找总价格为目标值的两个商品
 */
public class HeWeiSdeLiangGeShuZiLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 HeWeiSdeLiangGeShuZiLcof fun=new HeWeiSdeLiangGeShuZiLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //固定一遍，在另外一个区间二分，最坏Onlogn
    public int[] twoSum1(int[] price, int target) {
		for (int i = 0; i < price.length; i++) {
			int l=i+1,r=price.length-1;
			while (l<=r){
				int mid=l+(r-l)/2;
				if (price[mid]==target-price[i]){
					return new int[]{price[i],price[mid]};
				}else if (price[mid]<target-price[i]){
					l=mid+1;
				}else {
					r=mid-1;
				}
			}
		}
		return new int[0];
    }
	public int[] twoSum(int[] price, int target) {
		int i = 0, j = price.length - 1;
		while(i < j) {
			int s = price[i] + price[j];
			if(s < target) i++;
			else if(s > target) j--;
			else return new int[] { price[i], price[j] };
		}
		return new int[0];
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
